\documentclass[12pt]{beamer}
\usepackage{subfigure}
\usetheme{Oxygen}
%\usepackage{czech}
\usepackage{thumbpdf}
\usepackage{wasysym}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{pgf,pgfarrows,pgfnodes,pgfautomata,pgfheaps,pgfshade}
\usepackage{verbatim}
\usepackage{xcolor}

\pdfinfo
{
  /Title       (Programovani s omezujicimi podminkami v Scheduling
  		  Toolboxu)
  /Keywords     (CP)
  /Subject	(Bakalarska prace)
  /Creator     (TeX)
  /Author      (Jiri Cigler)
}


\title{Programování s~omezujícími podmínkami v~Scheduling Toolboxu}
\subtitle{Bakalářská práce \\ Vedoucí: Ing. Jan Kelbel}
\author{Jiří Cigler}
\date{27.6.2007}

\begin{document}

\frame{\titlepage}

\section*{}
\begin{frame}
  \frametitle{Obsah}
  \tableofcontents[section=1,hidesubsections]
\end{frame}

%\AtBeginSection[]
%{
%  \frame<handout:0>
%  {
%    \frametitle{Obsah}
%    \tableofcontents[currentsection,hideallsubsections]
%  }
%}

%\AtBeginSubsection[]
%{
%  \frame<handout:0>
%  {
%    \frametitle{Obsah}
%    \tableofcontents[sectionstyle=show/hide,subsectionstyle=show/shaded/hide]
%  }
%}

\newcommand<>{\highlighton}[1]{%
  \alt#2{\structure{#1}}{{#1}}
}

\newcommand{\icon}[1]{\pgfimage[height=1em]{#1}}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%% Content starts here %%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Programování s omezujícími podmínkami}
	

\begin{frame}	
\frametitle{Omezující podmínky (CP)}
{\it{Constraint programming represents one of the closest approaches
	computer science has yet made to the Holy Grail of programming:
	the user states the problem, the computer solves it.}}

	\hfill Eugene C. Freuder, Constraints, Duben 1997

  \begin{block}{Práce s CP}
    \begin{itemize}
      \item Vytvoření modelu kombinatorického (optimalizačního)
	problému -- uživatel
      \item Propagace omezujících podmínek -- constraint solver (CS)
	\item Prohledávací algoritmy (DFS, BAB, LDS $\ldots$) -- CS
    \end{itemize}
  \end{block}
  \begin{itemize}
	\item Knihovna gecode (www.gecode.org)
  \end{itemize}
\end{frame}


\section{Shop}
\begin{frame}
\frametitle{Shop}
	\begin{block}{Značení}
		\begin{itemize}
			\item $\mathcal T$ množina úloh, $\mathcal{T} =
			\{T_{11}, T_{12},
			\ldots, T_{mn} \}$
			\item $\mathcal{J}$ množina jobů, $\mathcal{J} =
			\{ J_1, J_2,
			\ldots,
			J_m \}$,  $J_i
					=\{ T_{i1}, T_{i2}, \ldots,
					T_{in}\}$
			\item $\mathcal{P}$ množina strojů,
			$\mathcal{P} = \{ P_1, P_2,
			\ldots, P_k \}$
%			\item $\mu_{ij}$ Přiřazuje úloze stroj.
		\end{itemize}
	\end{block}
	\begin{block}{Zadání problémů}
		\begin{enumerate}
			\item Matice doby trvání úloh $\bf{p} = \left[
			\begin{array}{cc} p(T_{11}) & p(T_{12}) \\
				p(T_{21}) &
			p(T_{22}) \end{array} \right]$
			\item Matice přiřazení úloh strojům $\bf{r}$~$ = \left[
			\begin{array}{cc} P_1 & P_2 \\ P_1 & P_1
			\end{array} \right], P_1 \wedge P_2 \in
			\mathcal{P}$

		\end{enumerate}

	\end{block}
\end{frame}

\begin{frame}
	\frametitle{Job-shop}
	\begin{block}{Job-shop (JS)}
	\begin{itemize}
		\item Pořadí úloh v jobech je dané:  $T_{i1} \rightarrow
		T_{i2} \rightarrow \ldots		\rightarrow T_{in}$
		\item Každá úloha má přiřazený stroj.

	\end{itemize}
\end{block}

\setbeamercolor{uppercol}{fg=white,bg=oxygenorange}%
\setbeamercolor{lowercol}{fg=black,bg=oxygenlightgray}%
\begin{beamerboxesrounded}[upper=uppercol,lower=lowercol,shadow=true]{Příklad}


%\begin{example}{A}
\begin{columns}
\begin{column}{0.5\textwidth}

\begin{eqnarray}
	   {\bf p} &=& \left[\begin{array}{cc} 1 & 3  \\ 2 & 4
	\end{array} \right]\nonumber  \\ \nonumber { \bf r}  & =&
\left[\begin{array}{cc} 2 & 1 \\  1 & 2  \end{array} \right]
\nonumber
\end{eqnarray}
\end{column}
\begin{column}{0.5\textwidth}
{\includegraphics[width=0.8\textwidth]{jobshop.pdf}}
\end{column}\end{columns}
%\end{example}
\end{beamerboxesrounded}

\end{frame}

\begin{frame}\frametitle{Flow-shop}
	\begin{block}{Flow-shop (FS)}
	\begin{itemize}
		\item Joby využívají stroje ve stejném pořadí -- sloupce matice $\bf r$ jsou shodné.
		\item 
	$T_{i1} \rightarrow
		T_{i2} \rightarrow \ldots		\rightarrow T_{in}$

	\end{itemize}
	\end{block}
\setbeamercolor{uppercol}{fg=white,bg=oxygenorange}%
\setbeamercolor{lowercol}{fg=black,bg=oxygenlightgray}%
\begin{beamerboxesrounded}[upper=uppercol,lower=lowercol,shadow=true]{Příklad}


%\begin{example}{A}
\begin{columns}
\begin{column}{0.5\textwidth}

\begin{eqnarray}
	   {\bf p} &=& \left[\begin{array}{cc} 1 & 3  \\ 2 & 4
	\end{array} \right]\nonumber  \\ \nonumber { \bf r}  & =&
\left[\begin{array}{cc} 2 & 1 \\  2 & 1  \end{array} \right]
\nonumber
\end{eqnarray}
\end{column}
\begin{column}{0.5\textwidth}
{\includegraphics[width=0.8\textwidth]{flowshop.pdf}}
\end{column}\end{columns}
%\end{example}
\end{beamerboxesrounded}

\end{frame}


\begin{frame}\frametitle{Open-shop}

	\begin{block}{Open-shop (OS)}
		\begin{itemize}
			\item Žádné precedenční vazby mezi úlohami.
		\end{itemize}
	\end{block}
	\setbeamercolor{uppercol}{fg=white,bg=oxygenorange}%
\setbeamercolor{lowercol}{fg=black,bg=oxygenlightgray}%
\begin{beamerboxesrounded}[upper=uppercol,lower=lowercol,shadow=true]{Příklad}


%\begin{example}{A}
\begin{columns}
\begin{column}{0.5\textwidth}

\begin{eqnarray}
	   {\bf p} &=& \left[\begin{array}{cc} 1 & 3  \\ 2 & 4
	\end{array} \right]\nonumber  \\ \nonumber { \bf r}  & =&
\left[\begin{array}{cc} 2 & 1 \\  2 & 1  \end{array} \right]
\nonumber
\end{eqnarray}
\end{column}
\begin{column}{0.5\textwidth}
{\includegraphics[width=0.8\textwidth]{openshop.pdf}}
\end{column}\end{columns}
%\end{example}
\end{beamerboxesrounded}


\end{frame}
\section{Řešení problému}
\begin{frame}
	\frametitle{Řešení -- model}
	\begin{block}{Model}
		\begin{itemize}
			\item Úlohy $\rightarrow$ proměnné
			\item Precedence $\rightarrow$ omezující podmínky

			\item Hodnotící funkce $C_{max}$ -- minimalizace
			délky rozvrhu.
				\item \textit{Fiktivní úloha} -- uměle přidána jedna úloha,
			která musí být vykonána po všech ostatních --
			ohraničuje rozvrh.
			
		\end{itemize}
	\end{block}
\end{frame}
\begin{frame}
	\frametitle{Řešení -- vývojový diagram}
	\begin{center}
	{\includegraphics[width=0.95\textwidth]{../images/metapost/flowchart.pdf}}
	\end{center}
\end{frame}
\section{Výsledky}
\begin{frame}
	\frametitle{Výsledky -- Job-shop}
	\begin{figure}
  \begin{center}
    \mbox{
      \subfigure{\includegraphics[width=0.45\textwidth]{BAB_JOBSHOPpercent_s6_25_6__21_22.pdf} } \quad
      \subfigure{\includegraphics[width=.45\textwidth]{/home/jirka/programovani/jcjobshop/trunk/stats/BAB_JOBSHOPruntime_log__min1max6__25_6__22_7.pdf}} 
      }
  \end{center}
\end{figure}
\end{frame}
\begin{frame}
	\frametitle{Výsledky -- Flow-shop}

	\begin{figure}
  \begin{center}
    \mbox{
      \subfigure{\includegraphics[width=0.45\textwidth]{/home/jirka/programovani/jcjobshop/trunk/stats/BAB_FLOWSHOPpercent_s6_25_6__21_38.pdf} } \quad
      \subfigure{\includegraphics[width=.45\textwidth]{/home/jirka/programovani/jcjobshop/trunk/stats/BAB_FLOWSHOPruntime_log__min1max6__25_6__22_10.pdf}} 
      }
  \end{center}
\end{figure}


\end{frame}

\begin{frame}
	\frametitle{Výsledky -- Open-shop}
	\begin{figure}
  \begin{center}
    \mbox{
      \subfigure{\includegraphics[width=0.45\textwidth]{/home/jirka/programovani/jcjobshop/trunk/stats/BAB_OPENSHOPpercent_s6_25_6__21_42.pdf} } \quad
      \subfigure{\includegraphics[width=.45\textwidth]{/home/jirka/programovani/jcjobshop/trunk/stats/BAB_OPENSHOPruntime_log__min1max6__25_6__22_3.pdf}} 
      }
  \end{center}
\end{figure}
\end{frame}

\section{Objektový návrh}
\begin{frame}
	\frametitle{Objektový návrh}
	\begin{block}{Cíle}
	\begin{enumerate}
\item	Rozšířit Torsche Scheduling toolbox, aby umožňoval snazší práci
	s různými typy shopů.
\item Co nejvíce využít už vytvořené objekty s ohledem na jednoduchost a
přímočarost používání.
	\end{enumerate}
	\end{block}
	\begin{center}
	\includegraphics[width=.9\textwidth]{../../UML/shop-talk.pdf}
	\end{center}
\end{frame}
\section{Shrnutí}
\begin{frame}
\frametitle{Shrnutí}
\begin{block}{Algoritmus}
\begin{itemize}
	\item Řešení nejen JS, ale i FS a OS 
	\item Pouze 5\% problémů řešeno v čase řádově delším než je
	medián pro danou velikost problému.
\end{itemize}
\end{block}

\begin{block}{Objektový návrh}
\begin{itemize}
	\item Rozšíří TORSCHE Scheduling toolbox o možnost práce s
	shopy.
	\item Nyní je připraven k implementaci.
\end{itemize}
\end{block}
\end{frame}



\end{document}
